programming table are filled by a value to minimise three

. They are the main components of the Sellers algorithm and are

ater in this section. In the backward propagation stage, the best

t with the minimum edit distance is discovered. The alignment

used in the Sellers algorithm is shown in Table 7.1.

The alignment statistic of the Sellers algorithm. u and v are two amino acids.

δ(u, v) = 0

If u = v, match, no distance

δ(u, v) = 1

If u ് v, mismatch

δ(u, -) = 1

Gap inserted into the 2^nd sequence

δ(-, v) = 1

Gap inserted into the 1^st sequence

he forward propagation stage

distance between two sequences x and y is a linear sum of the

edit distances, each of which is the distance between a pair of

esidues from two sequences or a gap. The definition is shown

ݕሻൌ෍ߜሺݔ෤௜, ݕ෤௜ሻ

ே

௜ୀଵ

ൌߜሺݔ෤ଵ, ݕ෤ଵሻ൅ߜሺݔ෤ଶ, ݕ෤ଶሻ൅⋯ߜሺݔ෤ே, ݕ෤ேሻ

(7.3)

stands for the length of aligned sequences, ݔ෤௜ and ݕ෤௜ are the i^th

air of residues, ߜሺݔ෤௜, ݕ෤௜ሻ is the edit distance between ݔ෤௜ and ݕ෤௜.

ݔ෤௜∈ሼݔ, െሽ means that ݔ෤௜ can be a residue from sequence x or a

ch is denoted by the hyphen key. Similarly, ݕ෤௜∈ሼݕ, െሽ means

n be a residue from sequence y or a gap. In the latter discussion,

plified by ݔ௜ and ݕ෤௜ is simplified by ݕ௜ for the simplicity. The

quation clearly shows one important property of sequence

y alignment, i.e., the whole alignment can be linearly

sed to piece-wise sub-optimisation problems as aforementioned.

of this linearity, the above equation can be re-written as below,